package com.leetcode;


/**
 * 1330. 翻转子数组得到最大的数组值 (困难)
 * 给你一个整数数组 nums 。「数组值」定义为所有满足 0 <= i < nums.length-1 的 |nums[i]-nums[i+1]| 的和。
 * 你可以选择给定数组的任意子数组，并将该子数组翻转。但你只能执行这个操作 一次 。
 * 请你找到可行的最大 数组值 。
 */
public class LeetCode1330 {

    public static void main(String[] arg0) {
        int[] nums = new int[]{2, 3, 1, 5, 4};
        System.out.println("翻转子数组得到最大的数组值 = " + maxValueAfterReverse(nums));
    }

    public static int maxValueAfterReverse(int[] nums) {
        // 先求出没有做任何翻转时候的最大值
        int value = 0;
        int len = nums.length;
        for (int i = 0; i < len - 1; i++) {
            value += Math.abs(nums[i] - nums[i + 1]);
        }

        // 情况1: 整个数组做翻转，结果不变，忽略
        // 情况2: 数组中某一个数字做翻转，结果不变，忽略
        // 情况3: 翻转[0, n]的部分，1 <= n <= len-2
        // 情况4: 翻转[n, len - 1]的部分，1 <= n <= len - 2
        int max1 = 0;
        for (int n = 1; n < len - 1; n++) { // 情况3 和 情况4合并在一个for循环中
            max1 = Math.max(max1, Math.abs(nums[0] - nums[n + 1]) - Math.abs(nums[n] - nums[n + 1]));
            max1 = Math.max(max1, Math.abs(nums[len - 1] - nums[n - 1]) - Math.abs(nums[n] - nums[n - 1]));
        }

        // 情况5: 翻转数组中间的任何一部分
        int max2 = Integer.MIN_VALUE, min2 = Integer.MAX_VALUE;
        for (int i = 0; i < len - 1; i++) {
            int x = nums[i], y = nums[i + 1];
            max2 = Math.max(max2, Math.min(x, y));
            min2 = Math.min(min2, Math.max(x, y));
        }

        return value + Math.max(max1, 2 * (max2 - min2));
    }

}
